package com.nanbei.hashtable;


/**
 * @ClassDescription:
 * @JdkVersion: 1.8
 * @Author: libs
 * @Created: 2024/6/20 14:54
 */
public class HashTable {

    static class Entry {
        int hash; // 哈希码
        Object key; // 键
        Object value; // 值
        Entry next;  // 指向下一个指针

        public Entry() {
        }

        public Entry(int hash, Object key, Object value) {
            this.hash = hash;
            this.key = key;
            this.value = value;
        }
    }

    Entry[] table = new Entry[16];
    int size = 0; // 元素个数
    float loadFactor = 0.75f;
    int threshold = (int) (table.length * loadFactor);


    /**
     * 根据 hash码 和 key 来获取值
     * <p>
     * 将求模运输替换成位运算
     * - 前提条件：数组的长度为 2 的 n 次方
     * - hash % 数组长度 = hash & （数组长度 -1）
     *
     * @param hash hash 码
     * @param key  键
     * @return value
     */
    Object get(int hash, Object key) {
        int index = hash & (table.length - 1);
        Entry entry = table[index];
        while (entry != null) {
            if (key.equals(entry.key)) {
                return entry.value;
            }
            entry = entry.next;
        }
        return null;
    }

    Object get( Object key) {
        int hash = key.hashCode();
        return get(hash,key);
    }

    /**
     * 向 hash 表中存入新的 key，value 如果
     *
     * @param hash  hash 码
     * @param key   键
     * @param value 值
     */
    public void put(int hash, Object key, Object value) {
        int index = hash & (table.length - 1);
        if (table[index] == null) {
            table[index] = new Entry(hash, key, value);

        } else {
            Entry entry = table[index];
            while (entry != null) {
                if (key.equals(entry.key)) {
                    entry.value = value;
                    return;
                }
                if (entry.next == null) {
                    entry.next = new Entry(hash, key, value);
                    break;
                }
                entry = entry.next;
            }

        }
        size++;
        if (size > threshold) {
            resize();
        }
    }

    public void put(Object key, Object value) {
        put(key.hashCode(),key,value);
    }


    /**
     * 根据 hash 码和 key删除value,并将value返回
     *
     * @param hash hash 码
     * @param key  键
     * @return 删除的value
     */
    Object remove(int hash, Object key) {
        int index = hash & (table.length - 1);
        if (table[index] == null) {
            return null;
        } else {
            Entry entry = table[index];
            if (entry.key == key) {
                table[index] = entry.next;
                size--;
                return entry.value;
            }
            Entry per = entry;
            entry = entry.next;
            while (entry != null) {
                if (key.equals(entry.key)) {
                    per.next = entry.next;
                    size--;
                    return entry.value;
                }
                per = entry;
                entry = entry.next;
            }

        }
        return null;
    }

    Object remove( Object key) {
        return remove(key.hashCode(),key);
    }


    /**
     * hashTable进行扩容
     * <p>
     * <p>
     * 拆分链表，移动到新数组，拆分规律
     * 一个链表最多拆成两个
     * hash & table.length == 0 的一组
     * hash & table.length != 0 的一组
     */
    private void resize() {
        Entry[] newTable = new Entry[table.length << 1];
        for (int i = 0; i < table.length; i++) {
            Entry bef = new Entry();
            Entry af = new Entry();
            Entry befEntry = null;
            Entry afEntry = null;
            if (table[i] != null) {
                Entry entry = table[i];
                while (entry != null) {
                    if ((entry.hash & table.length) == 0) {
                        bef.next = entry;
                        if (befEntry == null) {
                            befEntry = bef.next;
                        }
                        bef = bef.next;
                        entry = entry.next;
                        bef.next = null;
                    } else {
                        af.next = entry;
                        if (afEntry == null) {
                            afEntry = af.next;
                        }
                        af = af.next;
                        entry = entry.next;
                        af.next = null;
                    }

                }
                if (befEntry != null) {
                    newTable[i] = befEntry;
                }
                if (afEntry != null) {
                    newTable[i + table.length] = afEntry;
                }
            }
        }
        table = newTable;
        threshold = (int) (loadFactor * table.length);
    }

    public static void main(String[] args) {
        String s ="aaa";
        String sq = new String("aaa");
        System.out.println(s ==sq);
        System.out.println(s.hashCode());
        System.out.println(sq.hashCode());
        System.out.println(System.identityHashCode(s));
        System.out.println(System.identityHashCode(sq));
    }


}
